﻿namespace Leetcode.N0336;
public class Solution
{
    public IList<IList<int>> PalindromePairs(string[] words)
    {
        TrieReverse trie = new TrieReverse();
        for (int i = 0; i < words.Length; i++)
        {
            var word = words[i];
            trie.Insert(word, i);
        }

        IList<IList<int>> result = new List<IList<int>>();

        for (int i = 0; i < words.Length; i++)
        {
            this.Scan(words[i], i, trie, result);
        }

        return result;
    }

    private void Scan(string word, int wordIndex, TrieReverse trie, IList<IList<int>> result)
    {
        // 处理空字符串节点
        this.CheckTrieNode(word, wordIndex, trie, result);

        int findedIndex = -1;
        for (int i = 0; i < word.Length; i++)
        {
            var curNode = trie?.children?[word[i] - 'a'];

            if (curNode == null)
            {
                return;
            }

            findedIndex = i;

            this.CheckTrieNode(word, wordIndex, curNode, result);

            trie = curNode;
        }

        // 匹配到最后一个字符是回文字，再查字符串比当前更长的字符串
        if (findedIndex == word.Length - 1 || word == "")
        {
            this.ScanOtherTrieNodes(word, wordIndex, trie, result);
        }
    }

    private void CheckTrieNode(string word, int wordIndex, TrieReverse trie, IList<IList<int>> result)
    {
        if (trie?.value == null)
        {
            return;
        }

        if (!this.CanMergeToPalindromePairs(word, trie.value))
        {
            return;
        }

        foreach (var item in trie.wordIndexes)
        {
            if (wordIndex == item)
            {
                continue;
            }
            result.Add(new List<int> { wordIndex, item });
        }
    }

    private void ScanOtherTrieNodes(string word, int wordIndex, TrieReverse trie, IList<IList<int>> result)
    {
        if (trie?.children == null)
        {
            return;
        }

        foreach (var item in trie.children)
        {
            if (item == null)
            {
                continue;
            }

            this.CheckTrieNode(word, wordIndex, item, result);

            this.ScanOtherTrieNodes(word, wordIndex, item, result);
        }

    }

    private bool CanMergeToPalindromePairs(string word1, string word2)
    {
        if (word1 == null || word2 == null)
        {
            return false;
        }

        for (int i = 0; i < word1.Length && i < word2.Length; i++)
        {
            if (word1[i] != word2[word2.Length - 1 - i])
            {
                return false;
            }
        }
        if (word1.Length > word2.Length)
        {
            if (!this.IsPalindromePairs(word1, word2.Length, word1.Length - 1))
            {
                return false;
            }
        }

        else if (word1.Length < word2.Length)
        {
            if (!this.IsPalindromePairs(word2, 0, word2.Length - word1.Length - 1))
            {
                return false;
            }
        }
        return true;
    }

    private bool IsPalindromePairs(string word, int from, int to)
    {
        for (int i = from; i <= from + (to - from) / 2; i++)
        {
            if (word[i] != word[to - (i - from)])
            {
                return false;
            }
        }
        return true;
    }

    /// <summary>
    /// 后缀树
    /// </summary>
    private class TrieReverse
    {

        public string value;
        public TrieReverse[] children;
        public IList<int> wordIndexes;

        public TrieReverse()
        {
        }


        public void Insert(string word, int wordIndex)
        {
            if (word == "")
            {
                this.value = "";
                if (this.wordIndexes == null)
                {
                    this.wordIndexes = new List<int>();
                }
                this.wordIndexes.Add(wordIndex);
                return;
            }

            this.Insert(word, wordIndex, word.Length - 1);
        }

        private void Insert(string word, int wordIndex, int index)
        {
            if (this.children == null)
            {
                this.children = new TrieReverse[26];
            }

            var node = this.children[word[index] - 'a'];
            if (node == null)
            {
                node = new TrieReverse();
                this.children[word[index] - 'a'] = node;
            }

            if (index == 0)
            {
                node.value = word;
                if (node.wordIndexes == null)
                {
                    node.wordIndexes = new List<int>();
                }
                node.wordIndexes.Add(wordIndex);
            }
            else
            {
                node.Insert(word, wordIndex, index - 1);
            }
        }
    }
}
